\documentclass{assn}
\num{Lab 02 Proposal}
\by{Ian Voysey (iev@), Ryan Hofler (rhofler@)}
\due{14 September 2008, 23:50}
\for{15-440: Fund. Systems}
\usepackage{float}
\usepackage{graphicx}

\begin{document}
This proposal generally outlines a clone of the classic Atari ``Chip's
Challenge,'' with the eventual addition of a two-player mode over a network
connection. At least at first, this is to be a very plain clone in appearance ,
focusing more on the internals of the game than the chrome associated with
commercial playability.

\section{Requirements}
\subsection{Environment, Game Board}
The environment is a $n\times n$ grid, populated with different types of
tiles. These dictate the possible movement of the player: stepping on a
fire-tile without asbestos boots would cause the player to die; players cannot
walk through walls; players may always step on ground-tiles; players can
choose to push dirt blocks into water-tiles to make new ground-tiles;
movement-tiles force a player to go one block in a certain direction; players
cannot pass through door-tiles without holding the correct color key; etc.

The board will be stored as a matrix of \texttt{Tile}s, where \texttt{Tile} is
an interface abstracting the general notion of a tile, and what items and
players reside on them. Specific subscribing classes of \texttt{Tile} will
contain the notions of each of the types of tile (\texttt{FireTile},
\texttt{WaterTile}, etc.).

Adjacent to the game board will be a general status window, indicating how
many chips are left to be collected in the environment, what items the player
holds, and how many seconds he has left to complete the map.

\begin{figure}[H]
      \centering
      \includegraphics[scale=0.5]{screen}
      \caption{A screenshot of the original client, showing several of the
        interesting game items and tile types}
    \end{figure}

\subsection{Players}
The original game was only a single player environment, so this area will take
a certain amount of design work. With the introduction of multiple players, we
propose to add a co-op race mode. That is to say, both players live on the
same board, and work together to collect all the chips to finish the level,
but whoever collects the most chips (i.e. is the most effective
player) is said to win that level. 

In addition to integrating multiplay, this co-op mode creates the need for
item movement between players. For example, if Player $A$ has the key to a
door on the other side of a pool of water, and Player $B$ has the only
flippers available on the map, they cannot finish the level until a trade
occurs so that one player has at least those two items.

Each player must know, therefore, where he is in the world, what items he
holds, and how he is to interact with the (eventual) server.

It's not out of the question to extend this notion to $k$ players, but we
currently choose not to, due to the overhead of designing playable maps for a
large party of players. The engine will be written in a fully robust way with
respect to concurrency and scalability issues, but simply not used that way.

\subsection{Goals}
In either a single or multiplayer mode, the goal is to collect all the chips
on the board in the allotted time, necessarily using the items and keys on the
map to get past locked doors and over the different types of tiles.

\subsection{Objects}
The object of primary interest is chips---by definition, a level may only be
cleared when all the chips have been collected.

Of secondary interest are the various ability modifying items, each allowing
the player to overcome one type of obstacle. These, then, include
asbestos-boots for fire-tiles, flippers for water-tiles, sucker-boots for
movement-tiles, and ice skates for ice-tiles.

Lastly, players must be concerned with keys. These are one-time-use keys,
coded by color for specific doors.

Chips may not be traded between players, but the other objects may move
freely.

To implement this structure, we'll use a standard inheritance hierarchy to
allow the use (abuse) of \texttt{Java.util.collections}. Items will be
associated with grid positions while unclaimed, and moved to the player's
control when tripped. This will be a main source of interesting concurrency
control.

\subsection{Menu}
A simple menu will be available to the player, including mode selection,
simple game rules, and information about the authors. 

The primary non-trivial submenu will only occur once the game is taken to a
multiplayer level. We propose to follow the Counter-Strike model of having the
user peruse a list of available servers and select one with a need for
players. This enforces a better abstraction boundary between client and server,
and makes for a centralized server pool to be set up relatively easily. Since
we don't have \texttt{Battle.net} to rely on, this will involve manually
entering the IP/URL of the server, at least in the short term.

\subsection{Network Code}
The first single player version will be written without network code. The
benefit here is that the first version will roll out relatively quickly. This
happens at the cost of refactoring the code into a server and client for the
second version.

To make this refactoring as painless as possible, the board will be strongly
abstracted away from the player in the non-networked version. The player will
only know that he's writing to a board, so that the board can be swapped out
transparently for a network interface connecting to the One True Board later.

In the networked version, there will be one central server storing all of the
environment data for a particular game---this is almost entirely encapsulated
into the notion of the board. All of the concurrency control will happen here
as well, with each client taking taking turns with a mutex.

\subsection{Concurrency}
The single player version contains no concurrency issues to speak of, since
there is only one agent acting on the board ever.

The multiplayer version, however, brings in the whole slew of concurrency
issues associated with multiple agents, as well as the problems with network
lag of a client-server model. The One True Board will be stored server side,
and guarded by a mutex. The item list will be locked independently.

Having one mutex for the board might end up killing performance. If that's the
case, we might try to have mutexes for chunks of the board. Since the whole
map may well be larger than any one player's viewing window, it ought to not be
possible possible for concurrent issues to arise if the viewing windows are
disjoint.

\section{Debug and Testing}
Single player mode is straight forward to test, in that one must only assure
that all of the invariants are upheld: time decreases consistently; picking up
chips decreases the global chip count; stepping on a bad tile without adequate
protection kills the player and restarts the level; etc.

This gets more complicated with the introduction of networks and concurrent
access of the board. If there were one unified way to debug concurrency
issues, the world at large would be a better place. We're not entirely sure
how the testing will work out to be more rigorous than just ``trying to break
it a lot'', but there are some features (god-mode, reset button, etc.) that
can be added to make that testing go faster.
\end{document}
